% Created 2019-05-21 二 18:45
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\input{preamble.tex}
\author{wu}
\date{\today}
\title{Logic and Game Theory}
\hypersetup{
 pdfauthor={wu},
 pdftitle={Logic and Game Theory},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 26.1 (Org mode 9.1.14)}, 
 pdflang={English}}
\begin{document}

\maketitle
\tableofcontents


\section{Lec 2 An invitation to game theory}
\label{sec:org3f557e1}
Every game has three main ingredients:
\begin{enumerate}
\item the set of players, \([n]=\lb 1,2,\dots,n\rb\)
\item the rule of game
\item \textbf{outcomes} or winning conditions
\end{enumerate}


The game arena, that gives the rules of the game, can be envisaged as a finite
graph
\begin{itemize}
\item vertices denote game positions
\item edges correspond to moves
\item each vertex is labelled by the player whose turn it is to move
\item winning conditions are not present in the arena
\end{itemize}


Game tree: the tree unfolding of a game arena is \textbf{extensive form}


Consider two-person zero-sum games of perfect information. \(N=\lb 1,2\rb\).
\(\Sigma=\lb a_1,a_2,\dots,a_m\rb\) is a finite set of action symbols,
representing move of players, common for both players. Such games are referred
as \textbf{bipartisan games}


A \textbf{game arena} is a graph 
\(\calg=(W,\to,s_0)\) with \(W=\bcup_{i\in N}W^i\bcup\lb W^\text{leaf}\rb\). For
\(i\in N, W^i\) is the set of \emph{game positions} for player \(i\) and \(W^\text{leaf}\)
is the set of terminal game positions. \(s_0\) is the initial node of the game.
\(\to:(W\times \Sigma)\to W\), is a partial function called the move function


If a player \(i\) owns the game position \(s_0, s_0\in W^i\) then she picks an
action \(a'\) and moves to token to \(s'\), \(s_0\xrightarrow{a} s'\)
A play in \(calg\) is a path \(\rho:s_0a_0s_1a_1\dots\) where 
\(\forall j:s_j\xrightarrow{a_j}s_{j+1}\)


let \(\calg_t\) denote the tree unfolding of the arena \(\calg\). A \textbf{strategy} for
player \(i,\mu=(W_\mu,\to_\mu,s_0)\) is a maximal connected subtree of \(\calg_T\)
where for each player \(i\) node, there is a unique outgoing edge and for the
other player every move is included. That is, for \(s\in W_\mu\), if \(s\in
  W^i_\mu\) then there exists a unique \(a\in\Sigma\) s.t. \(s\xrightarrow{a}_\mu
  s'\) where we have \(s\xrightarrow{a}_T s'\). If \(s\in W_\mu^j(j\neq i)\), then
for each \(s'\) s.t. \(s\xrightarrow{a}_Ts'\), we have \(s\xrightarrow{a}_\mu s'\) 


A \textbf{strategy profile} is a pair \(<\mu,\tau>\) that fixes a strategy for each
player. A \textbf{winning strategy} \(\sigma\) for player \(i\) if every strategy \(\tau\) of
the opponent \(i\) wins.


A win/lose game is \textbf{determined} if starting from any game position, one of the
players has a winning strategy


\begin{theorem}
In every \textbf{finite} extensive form game of perfect information, we can compute whether
player $i$ can win. (Zermelo 1913)
\end{theorem}
\begin{proof}
Backward induction
\end{proof}

\subsection{Analysis of Nim}
\label{sec:org5f4e385}
\begin{lemma}
For all $m,n\ge0, (m,n)$ is winning iff $m\neq n$
\end{lemma}

Every finite extensive form game is of the form \(0\) or
\begin{equation*}
g_1+g_2+\dots+g_m
\end{equation*}
0 is the empty game, where no player can make any move
, \(g_1,g_2,\dots,g_m\) are subgames


If \(g=g_1+\dots+g_m, h=h_1+\dots+h_m\), then
\begin{equation*}
g+h=(g_1+h)+\dots+(g_m+h)+(g+h_1)+\dots+(g+h_n)
\end{equation*}
When \(g\) is a subgame of \(h\), we write \(g\le h\)


\textbf{\(g_1\equiv g_2\)} if for all \(h\), \(g_1+h\) is winning(losing) iff \(g_2+h\) is
winning(losing).


\(\equiv\) is an equivalence relation


\begin{lemma}[The loser's lemma]\leavevmode
If $g$ is losing then $g\equiv 0$
\end{lemma}

\begin{proof}
\;\par
\begin{enumerate}
\item fix a losing game $g$
\item prove: for all $h, g+h$ is losing iff $h$ is losing
\item Assuming this, suppose $h$ is winning, then there is a move to $h'$
that is losing. Hence $g+h'$ is losing and $g+h$ is winning
\end{enumerate}
\end{proof}


\begin{lemma}
If $h$ and $g$ are losing, so is $g+h$
\end{lemma}
\begin{proof}
IH1(inductive hypothesis): for all $g'\le g$, if $h$ is losing, then so is $g'+h$

IH2: for all $h'\le h$, if $h$ is losing, then so is $g+h'$

Every initial move in $g+h$ is either in $g$ or $h$. First consider the latter.
$h$ is losing, so every move in $h$ to $h'$ is winning
\end{proof}


\begin{corollary}
if $h$ is losing, then for all $g$, $g+h=g$
\end{corollary}
\section{lec3: Normal form games}
\label{sec:org57bf819}
\(N=\{1,2,\dots,n\}\) the set of players

For each \(i\in N\), a \textcolor{red}{finite} set \(S_i=\{1,\dots,m_i\}\) of 
\textcolor{cyan}{pure strategies} 
\end{document}